#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        if(nums[0]!=0) return 0;
        //题目中，原数组是单调递增的，所以可以使用二分法
        //并且每个数只会出现一次，即表示，一旦缺少，则可通过下标判断出错位
        int l=1,r=nums.size();
        int mid = (l+r)/2;
        int ans = 0;
        while(l<r) {
            if(nums[mid]!=mid && nums[mid-1] == mid-1){
                return nums[mid]-1;
            }
            else if(nums[mid] == mid){
                l=mid+1;
                mid = (l+r)/2;
            }else{
                r=mid;
                mid = (l+r)/2;
            }
        }
        return nums.size();
    }

};
int main(){
    vector<int> nums = {0,1};
    cout<<Solution().missingNumber(nums)<<endl;
    return 0;
}